package MyBinaryTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-15
 * Time: 19:29
 */

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class BinaryTree {

    /**
     * 创建二叉树节点TreeNode
     */
    static class TreeNode{
        public char val;//节点的值
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode(char val){
            this.val = val;
        }
    }
    /**
     * 创建一个二叉树
     */
    public TreeNode CreateBinaryTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        A.left  = B;
        A.right = C;
        B.left  = D;
        C.left  = E;
        C.right = F;
        return A;
    }
    /**
     * 二叉树的前序遍历----------->根左右
     */
    public void PrevOrder(TreeNode root){
        if(root==null) return;
        System.out.print(root.val+" ");
        PrevOrder(root.left);
        PrevOrder(root.right);
    }

    /**
     * 二叉树返回值为ListNode<>版
     */




    /**
     * 二叉树前序遍历------>子问题思路
     */



    /**
     * 二叉树的前中序遍历-------->左根右
     */
    public void InOrder(TreeNode root){
        if(root==null) return;
        PrevOrder(root.left);
        System.out.print(root.val+" ");
        PrevOrder(root.right);
    }

    /**
     * 二叉树的后序遍历----------->左右根
     */
    public void PostOrder(TreeNode root){
        if(root==null) return;
        PrevOrder(root.left);
        PrevOrder(root.right);
        System.out.print(root.val+" ");
    }

    /**
     * 遍历思路求二叉树节点的个数
     * @param root
     * @return
     */
    public static int cnt =0;
    public int size(TreeNode root){
         if(root==null) return 0;
         cnt++;
         size(root.left);
         size(root.right);
         return cnt;
    }

    /**
     * 子问题思路求二叉树节点的个数
     * @param root
     * @return
     */
   // public static int cnt =0;
    public int size1(TreeNode root){
        if(root==null) return 0;
        return size1(root.left)+size1(root.right)+1;
    }


    /**
     * 求叶子节点的个数---->遍历思路
     */
    public static int leafSize =0;
    public int getLeafNodeSize(TreeNode root){
        if(root==null) return 0;

        getLeafNodeSize(root.left);
        getLeafNodeSize(root.right);
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        return leafSize;
    }


    /**
     * 求叶子节点的个数---->子问题思路
     */
    public int getLeafNodeSize2(TreeNode root){
        if(root==null) return 0;
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeSize2(root.left)+getLeafNodeSize2(root.right);
    }

    /**
     * 获取第k层节点的个数
     */

    public int getLevelNodeValue(TreeNode root,int k) {
        if(root==null) return 0;
        if(k==1) return 1;
        int leftTree = getLevelNodeValue(root.left,k-1);
        int rightTree = getLevelNodeValue(root.right,k-1);
        return leftTree+rightTree;
    }

    /**
     * 求二叉树的高度
     */

    public int getHeight(TreeNode root){
        if(root==null) return 0;
        int leftTree = getHeight(root.left);
        int rightTree =getHeight(root.right);
        return leftTree>rightTree?leftTree+1:rightTree+1;
    }

    /**
     * 二叉树查找你要找的节点
     */
    public TreeNode find(TreeNode root,char val){
        if(root==null) return null;
        if(root.val==val) return root;
        //否则去左子树找，返回的节点也要接收
        TreeNode ret = find(root.left,val);//去左子树
        if(ret!=null){//如果ret不为空证明找到了，那就返回这个节点的值
            return ret;
        }
        //同样的去右子树找，如果不为空则证明找到了，为空就是没有找到继续递归寻找
        ret = find(root.right,val);
        if(ret!=null){
            return ret;
        }
        return null;//没有找到就返回null

    }


//    public TreeNode find(TreeNode root,char val){
//        if(root==null) return null;
//        if(root.val==val){
//            return root;
//        }
//        //去左子树找
//        TreeNode ret = find(root.left,val);
//        if(ret!=null){
//            return ret;
//        }
//
//        ret = find(root.right,val);
//        if(ret!=null){
//            return ret;
//        }
//        return null;
//     }

    /**
     * 二叉树的层序遍历,刚开始把根节点的值放到cur里面去，如果队列不为空就将cur弹出，同时将cur的left和right放入队列中
     */
    Queue<TreeNode> queue = new LinkedList<>();
    public void levelOrder(TreeNode root){
        if(root==null) return;
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur =queue.poll();
            System.out.print(cur+" ");
            if(root.left!=null)
            queue.offer(root.left);
            if(root.right!=null)
            queue.offer(root.right);
        }
    }



    public Boolean isCompleteTree(TreeNode root){
        if(root==null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur!=null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }

        return false;
    }


    


}
